<!DOCTYPE html>
<html lang="zh-CN">
  <head>
  <meta charset="UTF-8">
  <meta 
    name="viewport"
    content="width=device-width, initial-scale=1.0, minimum-scale=1.0">
  <meta 
    http-equiv="X-UA-Compatible" 
    content="ie=edge">
  <meta 
    name="theme-color" 
    content="#fff" 
    id="theme-color">
  <meta 
    name="description" 
    content="霜序廿的个人网站">
  <link 
    rel="icon" 
    href="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg">
  <title>javascript背包问题详解</title>
  
    
      <meta 
        property="og:title" 
        content="javascript背包问题详解">
    
    
      <meta 
        property="og:url" 
        content="https://shuangxunian.github.io/2021/10/17/fullExplanationOfTheBackpackProblemOfJavascript/index.html">
    
    
      <meta 
        property="og:img" 
        content="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg">
    
    
      <meta 
        property="og:img" 
        content="如题目">
    
    
      <meta 
        property="og:type" 
        content="article">
      <meta 
        property="og:article:published_time" 
        content="2021-10-17">
      <meta 
        property="og:article:modified_time" 
        content="2021-10-17">
      <meta 
        property="og:article:author" 
        content="霜序廿">
      
        
          <meta 
            property="og:article:tag" 
            content="js">
        
          <meta 
            property="og:article:tag" 
            content="算法">
        
      
    
  
  <script>
    function loadScript(url, cb) {
      var script = document.createElement('script');
      script.src = url;
      if (cb) script.onload = cb;
      script.async = true;
      document.body.appendChild(script);
    }
    function loadCSS(href, data, attr) {
      var sheet = document.createElement('link');
      sheet.ref = 'stylesheet';
      sheet.href = href;
      sheet.dataset[data] = attr;
      document.head.appendChild(sheet);
    }
    function changeCSS(cssFile, data, attr) {
      var oldlink = document.querySelector(data);
      var newlink = document.createElement("link");
      newlink.setAttribute("rel", "stylesheet");
      newlink.setAttribute("href", cssFile);
      newlink.dataset.prism = attr;
      document.head.replaceChild(newlink, oldlink);
    }
  </script>
  
    
      
      
      
      
        
        
        
        <script>
          function prismThemeChange() {
            if(document.getElementById('theme-color').dataset.mode === 'dark') {
              if(document.querySelector('[data-prism]')) {
                changeCSS('/js/lib/prism/prism-tomorrow.min.css', '[data-prism]', 'prism-tomorrow');
              } else {
                loadCSS('/js/lib/prism/prism-tomorrow.min.css', 'prism', 'prism-tomorrow');
              }
            } else {
              if(document.querySelector('[data-prism]')) {
                changeCSS('/js/lib/prism/prism.min.css', '[data-prism]', 'prism');
              } else {
                loadCSS('/js/lib/prism/prism.min.css', 'prism', 'prism');
              }
            }
          }
          prismThemeChange()
        </script>
      
      
        
        <link rel="stylesheet" href="/js/lib/prism/prism-line-numbers.min.css">
      
    
  
  <script>
    // control reverse button
    var reverseDarkList = {
      dark: 'light',
      light: 'dark'
    };
    var themeColor = {
      dark: '#1c1c1e',
      light: '#fff'
    }
    // get the data of css prefers-color-scheme
    var getCssMediaQuery = function() {
      return window.matchMedia('(prefers-color-scheme: dark)').matches ? 'dark' : 'light';
    };
    // reverse current darkmode setting function
    var reverseDarkModeSetting = function() {
      var setting = localStorage.getItem('user-color-scheme');
      if(reverseDarkList[setting]) {
        setting = reverseDarkList[setting];
      } else if(setting === null) {
        setting = reverseDarkList[getCssMediaQuery()];
      } else {
        return;
      }
      localStorage.setItem('user-color-scheme', setting);
      return setting;
    };
    // apply current darkmode setting
  </script>
  
    <script>
      var setDarkmode = function(mode) {
      var setting = mode || localStorage.getItem('user-color-scheme');
      if(setting === getCssMediaQuery()) {
        document.documentElement.removeAttribute('data-user-color-scheme');
        localStorage.removeItem('user-color-scheme');
        document.getElementById('theme-color').content = themeColor[setting];
        document.getElementById('theme-color').dataset.mode = setting;
        prismThemeChange();
      } else if(reverseDarkList[setting]) {
        document.documentElement.setAttribute('data-user-color-scheme', setting);
        document.getElementById('theme-color').content = themeColor[setting];
        document.getElementById('theme-color').dataset.mode = setting;
        prismThemeChange();
      } else {
        document.documentElement.removeAttribute('data-user-color-scheme');
        localStorage.removeItem('user-color-scheme');
        document.getElementById('theme-color').content = themeColor[getCssMediaQuery()];
        document.getElementById('theme-color').dataset.mode = getCssMediaQuery();
        prismThemeChange();
      }
    };
    setDarkmode();
    </script>
  
  
  <link rel="preload" href="//at.alicdn.com/t/font_1946621_i1kgafibvw.css" as="style" >
  <link rel="preload" href="//at.alicdn.com/t/font_1952792_89b4ac4k4up.css" as="style" >
  
  
    <link rel="preload" href="/js/lib/lightbox/baguetteBox.min.js" as="script">
    <link rel="preload" href="/js/lib/lightbox/baguetteBox.min.css" as="style" >
  
  
    <link rel="preload" href="/js/lib/lozad.min.js" as="script">
  
  
  
  
  
  
  
  <link rel="stylesheet" href="/css/main.css">
  
  <link rel="stylesheet" href="//at.alicdn.com/t/font_1946621_i1kgafibvw.css">
  
  <link rel="stylesheet" href="//at.alicdn.com/t/font_1952792_89b4ac4k4up.css">
  
    <link rel="stylesheet" href="/js/lib/lightbox/baguetteBox.min.css">
  
<meta name="generator" content="Hexo 5.4.0"></head>

  <body>
    <div class="wrapper">
       
      <nav class="navbar">
  <div class="navbar-logo">
    <span class="navbar-logo-main">
      
        <img 
          class="navbar-logo-img" 
          src="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg" 
          alt="blog logo">
      
      <span class="navbar-logo-dsc">霜序廿的个人网站</span>
    </span>
  </div>
  <div class="navbar-menu">
    
      <a 
        href="/" 
        class="navbar-menu-item">
        
          首页
        
      </a>
    
      <a 
        href="/archives" 
        class="navbar-menu-item">
        
          归档
        
      </a>
    
      <a 
        href="/tags" 
        class="navbar-menu-item">
        
          标签
        
      </a>
    
      <a 
        href="/categories" 
        class="navbar-menu-item">
        
          分类
        
      </a>
    
      <a 
        href="/about" 
        class="navbar-menu-item">
        
          关于
        
      </a>
    
      <a 
        href="/links" 
        class="navbar-menu-item">
        
          友链
        
      </a>
    
    <a 
      class="navbar-menu-item darknavbar" 
      id="dark">
      <i class="iconfont icon-weather"></i>
    </a>
    <a 
      class="navbar-menu-item searchnavbar" 
      id="search">
      <i 
        class="iconfont icon-search" 
        style="font-size: 1.2rem; font-weight: 400;">
      </i>
    </a>
  </div>
</nav> 
      
      <div 
        id="local-search" 
        style="display: none">
        <input
          class="navbar-menu-item"
          id="search-input"
          placeholder="请输入搜索内容..." />
        <div id="search-content"></div>
      </div>
      
      <div class="section-wrap">
        <div class="container">
          <div class="columns">
            <main class="main-column">
<article class="card card-content">
  <header>
    <h1 class="post-title">
      javascript背包问题详解
    </h1>
  </header>
  <div class="post-meta post-show-meta">
    <time datetime="2021-10-17T06:11:16.681Z">
      <i 
        class="iconfont icon-calendar" 
        style="margin-right: 2px;">
      </i>
      <span>2021-10-17</span>
    </time>
    
      <span class="dot"></span>
      
        <a 
          href="/categories/%E6%8A%80%E6%9C%AF%E6%96%87%E7%AB%A0/" 
          class="post-meta-link">
          技术文章
        </a>
      
    
    
      <span class="dot"></span>
      <span>6.3k 字</span>
    
  </div>
  
    <div 
      class="post-meta post-show-meta" 
      style="margin-top: -10px;">
      <div style="display: flex; align-items: center;">
        <i 
          class="iconfont icon-biaoqian" 
          style="margin-right: 2px; font-size: 1.15rem;">
        </i>
        
          
          <a 
            href="/tags/js/" 
            class="post-meta-link">
            js
          </a>
        
          
            <span class="dot"></span>
          
          <a 
            href="/tags/%E7%AE%97%E6%B3%95/" 
            class="post-meta-link">
            算法
          </a>
        
      </div>
    </div>
  
  </header>
  <div 
    id="section" 
    class="post-content">
    <h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>这是从司徒正美大佬和其他人那里整理来的，希望司徒大佬下辈子会开开心心，不要有太大压力；希望我们普通人也要注意身体，多运动多休息。</p>
<h2 id="引子"><a href="#引子" class="headerlink" title="引子"></a>引子</h2><p>打算好好学一下算法，先拿背包问题入手。但是网上许多教程都是C++或java或python，大部分作者都是在校生，虽然算法很强，但是完全没有工程意识，全局变量满天飞，变量名不明所以。我查了许多资料，花了一个星期才搞懂，最开始的01背包耗时最多，以前只会枚举（就是普通的for循环，暴力地一步步遍历下去），递归与二分，而动态规划所讲的状态表与状态迁移方程为我打开一扇大门。</p>
<h2 id="01背包问题"><a href="#01背包问题" class="headerlink" title="01背包问题"></a>01背包问题</h2><p>篇幅可能有点长，但请耐心看一下，你会觉得物有所值的。</p>
<h3 id="1-1-问题描述："><a href="#1-1-问题描述：" class="headerlink" title="1.1 问题描述："></a>1.1 问题描述：</h3><p>有${n}$件物品和${1}$个容量为W的背包。每种物品均只有一件，第${i}$件物品的重量为${weights[i]}$，价值为${values[i]}$，求解将哪些物品装入背包可使价值总和最大。</p>
<p>对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态只是1或0, 此问题称为<strong>01背包问题</strong>。</p>
<h3 id="1-2-问题分析："><a href="#1-2-问题分析：" class="headerlink" title="1.2 问题分析："></a>1.2 问题分析：</h3><p>数据：物品个数${n=5}$,物品重量${weights=[2，2，6，5，4]}$,物品价值${values=[6，3，5，4，6]}$,背包总容量${W=10}$。</p>
<p>我们设置一个矩阵${f}$​来记录结果，${f(i, j)}$​ 表示可选物品为 ${i…n}$​ 背包容量为 ${j(0&lt;=j&lt;=W)}$​ 时， 背包中所放物品的最大价值。</p>
<table>
<thead>
<tr>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
<th></th>
</tr>
</thead>
<tbody><tr>
<td>w</td>
<td>v</td>
<td>i\j</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
<td>6</td>
<td>7</td>
<td>8</td>
<td>9</td>
<td>10</td>
</tr>
<tr>
<td>2</td>
<td>6</td>
<td>0</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>1</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>6</td>
<td>5</td>
<td>2</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>5</td>
<td>4</td>
<td>3</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>6</td>
<td>4</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
</tbody></table>
<p>我们先看第一行，物品0的体积为2，价值为6，当容量为0时，什么也放不下，因此第一个格式只能填0，程序表示为${f(0,0) = 0}$或者${f[0][0] = 0}$。 当${j=1}$时，依然放不下${w_0}$，因此依然为0，${f(0, 1) = 0}$。 当${j=2}$时，能放下${w_0}$，于是有 ${f(0, 2)\ = \ v_0=6}$。 当${j=3}$时，也能放下${w_0}$，但我们只有一个物品0，因此它的值依然是6，于是一直到${j=10}$时，它的值都是${v_0}$。</p>
<table>
<thead>
<tr>
<th>w</th>
<th>v</th>
<th>i\j</th>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
<th>7</th>
<th>8</th>
<th>9</th>
<th>10</th>
</tr>
</thead>
<tbody><tr>
<td>2</td>
<td>6</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>1</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>6</td>
<td>5</td>
<td>2</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>5</td>
<td>4</td>
<td>3</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>6</td>
<td>4</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
</tbody></table>
<p>根据第一行，我们得到如下方程</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/90a78797-647d-4263-b2a1-90aa859c259b-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/90a78797-647d-4263-b2a1-90aa859c259b-3807603.jpg"></p>
<p>当背包容量少于物品面 积时，总价值为0，否则为物品的价值</p>
<p>然后我们看第二行，确定确定${f(1,0…10)}$这11个元素的值。当${j=0}$ 时，依然什么也放不下，值为0，但我们发觉它是上方格式的值一样的，${f(1,0)=0}$。 当${j=1}$时，依然什么也放不下，值为0，但我们发觉它是上方格式的值一样的，${f(1,1)=0}$. 当${j=2}$时，它可以选择放入物品1或不放。</p>
<p>如果选择不放物品1，背包里面有物品0，最大价值为6。</p>
<p>如果选择放入物品1，我们要用算出背包放入物品1后还有多少容量，然后根据容量查出它的价值，再加上物品1的价值，即${f(0,j-w_1)+v_1}$ 。由于我们的目标是尽可能装最值钱的物品， 因此放与不放， 我们需要通过比较来决定，于是有</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/e87239c0-982f-4c6a-8c3b-85f1461bf109-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/e87239c0-982f-4c6a-8c3b-85f1461bf109-3807603.jpg"></p>
<p>显然${v_1=2，v_0=6}$, 因此这里填${v_0}$。 当${j=3}$时， 情况相同。 当${j=4}$，能同时放下物品0与物品1，我们这个公式的计算结果也合乎我们的预期， 得到${f(1,4)=9}$。 当${j&gt;4}$时， 由于背包只能放物品0与物品1，那么它的最大价值也一直停留在${v_0+v_1=9}$</p>
<table>
<thead>
<tr>
<th>w</th>
<th>v</th>
<th>i\j</th>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
<th>7</th>
<th>8</th>
<th>9</th>
<th>10</th>
</tr>
</thead>
<tbody><tr>
<td>2</td>
<td>6</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
</tr>
<tr>
<td>6</td>
<td>5</td>
<td>2</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>5</td>
<td>4</td>
<td>3</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>6</td>
<td>4</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
</tbody></table>
<p>我们再看第三行，当${j=0}$时，什么都放不下，${f(2,0)=0}$。当${j=1}$时，依然什么也放不下，${f(2,1)=0}$，当${j=2}$时，虽然放不下${w_2}$，但我们根据上表得知这个容号时，背包能装下的最大价值是6。继续计算下去，其实与上面推导的公式结果是一致的，说明公式是有效的。当${j=8}$时，背包可以是放物品0、1，或者放物品1、2，或者放物品0、2。物品0、1的价值，我们在表中就可以看到是9，至于其他两种情况我们姑且不顾，我们目测就知道是最优值是${6+5=11}$， 恰恰我们的公式也能正确计算出来。当${j=10}$时,刚好三个物品都能装下，它们的总值为14，即${f(2,10)=14}$</p>
<p>第三行的结果如下：</p>
<table>
<thead>
<tr>
<th>w</th>
<th>v</th>
<th>i\j</th>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
<th>7</th>
<th>8</th>
<th>9</th>
<th>10</th>
</tr>
</thead>
<tbody><tr>
<td>2</td>
<td>6</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
</tr>
<tr>
<td>6</td>
<td>5</td>
<td>2</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>11</td>
<td>11</td>
<td>14</td>
</tr>
<tr>
<td>5</td>
<td>4</td>
<td>3</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>6</td>
<td>4</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
</tbody></table>
<p>整理一下第1，2行的适用方程：</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/7d6e8bb8-40e9-47eb-82bd-fbbd51351c11-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/7d6e8bb8-40e9-47eb-82bd-fbbd51351c11-3807603.jpg"></p>
<p>我们根据此方程，继续计算下面各列，于是得到</p>
<table>
<thead>
<tr>
<th>w</th>
<th>v</th>
<th>i\j</th>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
<th>7</th>
<th>8</th>
<th>9</th>
<th>10</th>
</tr>
</thead>
<tbody><tr>
<td>2</td>
<td>6</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
</tr>
<tr>
<td>6</td>
<td>5</td>
<td>2</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>11</td>
<td>11</td>
<td>14</td>
</tr>
<tr>
<td>5</td>
<td>4</td>
<td>3</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>10</td>
<td>11</td>
<td>13</td>
<td>14</td>
</tr>
<tr>
<td>4</td>
<td>6</td>
<td>4</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>12</td>
<td>12</td>
<td>15</td>
<td>15</td>
<td>15</td>
</tr>
</tbody></table>
<p>至此，我们就可以得到解为15.</p>
<p>我们最后根据0-1背包问题的最优子结构性质，建立计算${f(i,j)}$的递归式：</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/a0ba8618-3ef0-45c0-87ca-62adcff5b127-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/a0ba8618-3ef0-45c0-87ca-62adcff5b127-3807603.jpg"></p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">//by 司徒正美</span>
 <span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length <span class="token operator">-</span><span class="token number">1</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">]</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> <span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>j <span class="token operator">&lt;</span> weights<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//如果容量不能放下物品0的重量，那么价值为0</span>
           f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>
        <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span> <span class="token comment">//否则等于物体0的价值</span>
           f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> values<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> <span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//创建新一行</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
            <span class="token punctuation">&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>j <span class="token operator">&lt;</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//等于之前的最优值</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> 
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">var</span> a <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h3 id="1-3-各种优化："><a href="#1-3-各种优化：" class="headerlink" title="1.3 各种优化："></a>1.3 各种优化：</h3><h4 id="合并循环"><a href="#合并循环" class="headerlink" title="合并循环"></a>合并循环</h4><p>现在方法里面有两个大循环，它们可以合并成一个。</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
    <span class="token punctuation">&#125;</span>
   <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span> <span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
       <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> <span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//第一行</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> j <span class="token operator">&lt;</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">?</span> <span class="token number">0</span> <span class="token operator">:</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>j <span class="token operator">&lt;</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//等于之前的最优值</span>
                    f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
                <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                    f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> 
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>然后我们再认真地思考一下，为什么要孤零零地专门处理第一行呢？<code>f[i][j] = j &lt; weights[i] ? 0 : values[i]</code>是不是能适用于下面这一行<code>f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) </code>。Math.max可以轻松转换为三元表达式，结构极其相似。而看一下i-1的边界问题，有的书与博客为了解决它，会添加第0行，全部都是0，然后i再往下挪。其实我们也可以添加一个${-1}$行。那么在我们的方程中就不用区分${i==0}$与${0&gt;0}$的情况，方程与其他教科书的一模一样了！</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/6c2579cf-49cc-4458-bfde-c64d14377fc9-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/6c2579cf-49cc-4458-bfde-c64d14377fc9-3807603.jpg"></p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span>
    f<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n <span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//注意边界，没有等号</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">&lt;=</span><span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token comment">//注意边界，有等号</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> j <span class="token operator">&lt;</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//注意边界， 没有等号</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span>values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//case 3</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<table>
<thead>
<tr>
<th>w</th>
<th>v</th>
<th>i\j</th>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
<th>7</th>
<th>8</th>
<th>9</th>
<th>10</th>
<th></th>
</tr>
</thead>
<tbody><tr>
<td>X</td>
<td>X</td>
<td>-1</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td></td>
</tr>
<tr>
<td>2</td>
<td>6</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td>6</td>
<td></td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td></td>
</tr>
<tr>
<td>6</td>
<td>5</td>
<td>2</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>11</td>
<td>11</td>
<td>14</td>
<td></td>
</tr>
<tr>
<td>5</td>
<td>4</td>
<td>3</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>9</td>
<td>10</td>
<td>11</td>
<td>13</td>
<td>14</td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>6</td>
<td>4</td>
<td>0</td>
<td>0</td>
<td>6</td>
<td>6</td>
<td>9</td>
<td>9</td>
<td>12</td>
<td>12</td>
<td>15</td>
<td>15</td>
<td>15</td>
<td></td>
</tr>
</tbody></table>
<p>负一行的出现可以大大减少了在双层循环的分支判定。是一个很好的技巧。</p>
<p>注意，许多旧的教程与网上文章，通过设置二维数组的第一行为0来解决i-1的边界问题（比如下图）。当然也有一些思维转不过来的缘故，他们还在坚持数字以1开始，而我们新世代的IT人已经确立从0开始的编程思想。</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/371140fa-43d7-4fea-b60c-e66d74c1e169-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/371140fa-43d7-4fea-b60c-e66d74c1e169-3807603.jpg"></p>
<h4 id="选择物品"><a href="#选择物品" class="headerlink" title="选择物品"></a>选择物品</h4><p>上面讲解了如何求得最大价值，现在我们看到底选择了哪些物品，这个在现实中更有意义。许多书与博客很少提到这一点，就算给出的代码也不对，估计是在设计状态矩阵就出错了。</p>
<p>仔细观察矩阵，从${f(n-1,W)}$逆着走向${f(0,0)}$，设i=n-1,j=W，如果${f(i,j)}$==${f(i-1,j-w_i)+v_i}$说明包里面有第i件物品，因此我们只要当前行不等于上一行的总价值，就能挑出第i件物品，然后j减去该物品的重量，一直找到j = 0就行了。</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">//by 司徒正美</span>
<span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span>
    f<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token keyword">var</span> selected <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n <span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//注意边界，没有等号</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token comment">//创建当前的二维数组</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">&lt;=</span><span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//注意边界，有等号</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> j <span class="token operator">&lt;</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//注意边界， 没有等号</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token comment">//case 1</span>
            <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span>values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//case 2</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">var</span> j <span class="token operator">=</span> <span class="token constant">W</span><span class="token punctuation">,</span> w <span class="token operator">=</span> <span class="token number">0</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i<span class="token operator">=</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">>=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
         <span class="token keyword">if</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">></span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
             selected<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span>
             console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token string">"物品"</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span><span class="token string">"其重量为"</span><span class="token punctuation">,</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token string">"其价格为"</span><span class="token punctuation">,</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
             j <span class="token operator">=</span> j <span class="token operator">-</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
             w <span class="token operator">+=</span>  weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
         <span class="token punctuation">&#125;</span>
     <span class="token punctuation">&#125;</span>
    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token string">"背包最大承重为"</span><span class="token punctuation">,</span><span class="token constant">W</span><span class="token punctuation">,</span><span class="token string">" 现在重量为"</span><span class="token punctuation">,</span> w<span class="token punctuation">,</span> <span class="token string">" 总价值为"</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token keyword">return</span> <span class="token punctuation">[</span>f<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">,</span> selected<span class="token punctuation">.</span><span class="token function">reverse</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">]</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">var</span> a <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span>
<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/8dd1e40c-7b86-4230-8f51-25820c7a9243-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/8dd1e40c-7b86-4230-8f51-25820c7a9243-3807603.jpg"></p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/5a318fb6-bb0e-4a9a-a679-e435c08c2f20-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/5a318fb6-bb0e-4a9a-a679-e435c08c2f20-3807603.jpg"></p>
<h4 id="使用滚动数组压缩空间"><a href="#使用滚动数组压缩空间" class="headerlink" title="使用滚动数组压缩空间"></a>使用滚动数组压缩空间</h4><p>所谓滚动数组，目的在于优化空间，因为目前我们是使用一个${i<em>j}$的二维数组来储存每一步的最优解。在求解的过程中，我们可以发现，当前状态只与前一行的状态有关，那么更之前存储的状态信息已经无用了，可以舍弃的，我们只需要存储当前状态和前一行状态，所以只需使用${2</em>j}$的空间，循环滚动使用，就可以达到跟${i*j}$一样的效果。这是一个非常大的空间优化。</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">//by 司徒正美</span>
<span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length
    <span class="token keyword">var</span> lineA <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token keyword">var</span> lineB <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> lastLine <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> currLine 
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token punctuation">[</span>lineA<span class="token punctuation">,</span> lineB<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">//case1 在这里使用es6语法预填第一行</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> 
        currLine <span class="token operator">=</span> lastLine <span class="token operator">===</span> <span class="token number">0</span> <span class="token operator">?</span> <span class="token number">1</span> <span class="token operator">:</span> <span class="token number">0</span> <span class="token comment">//决定当前要覆写滚动数组的哪一行</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">&lt;=</span><span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            f<span class="token punctuation">[</span>currLine<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>lastLine<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token comment">//case2 等于另一行的同一列的值</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> j<span class="token operator">>=</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">&#123;</span>                         
                <span class="token keyword">var</span> a <span class="token operator">=</span> f<span class="token punctuation">[</span>lastLine<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
                <span class="token keyword">var</span> b <span class="token operator">=</span> f<span class="token punctuation">[</span>lastLine<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
                f<span class="token punctuation">[</span>currLine<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//case3</span>
            <span class="token punctuation">&#125;</span>
           
        <span class="token punctuation">&#125;</span>
        lastLine <span class="token operator">=</span> currLine<span class="token comment">//交换行</span>
   <span class="token punctuation">&#125;</span>
   <span class="token keyword">return</span> f<span class="token punctuation">[</span>currLine<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">var</span> a <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span>
<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>我们还可以用更hack的方法代替currLine, lastLine</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">//by 司徒正美</span>
<span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length
   
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">,</span> now <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">,</span> last <span class="token comment">//case1 在这里使用es6语法预填第一行</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> 
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">&lt;=</span><span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            f<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span><span class="token number">1</span><span class="token operator">-</span>now<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token comment">//case2 等于另一行的同一列的值</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> j<span class="token operator">>=</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">&#123;</span>                         
                <span class="token keyword">var</span> a <span class="token operator">=</span> f<span class="token punctuation">[</span><span class="token number">1</span><span class="token operator">-</span>now<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span>
                <span class="token keyword">var</span> b <span class="token operator">=</span> f<span class="token punctuation">[</span><span class="token number">1</span><span class="token operator">-</span>now<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
                f<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> b<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//case3</span>
            <span class="token punctuation">&#125;</span>
         <span class="token punctuation">&#125;</span>
         last <span class="token operator">=</span> f<span class="token punctuation">[</span>now<span class="token punctuation">]</span>
         now <span class="token operator">=</span> <span class="token number">1</span><span class="token operator">-</span>now <span class="token comment">// 1 - 0 => 1;1 - 1 => 0; 1 - 0 => 1 ....</span>
   <span class="token punctuation">&#125;</span>
   <span class="token keyword">return</span> last<span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">var</span> a <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span>
<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>注意，这种解法由于丢弃了之前N行的数据，因此很难解出挑选的物品，只能求最大价值。</p>
<h4 id="使用一维数组压缩空间"><a href="#使用一维数组压缩空间" class="headerlink" title="使用一维数组压缩空间"></a>使用一维数组压缩空间</h4><p>观察我们的状态迁移方程:</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/9681f216-4c66-41d5-add1-654431f662f3-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/9681f216-4c66-41d5-add1-654431f662f3-3807603.jpg"></p>
<p>weights为每个物品的重量，values为每个物品的价值，W是背包的容量，i表示要放进第几个物品，j是背包现时的容量（假设我们的背包是魔术般的可放大，从0变到W）。</p>
<p>我们假令i = 0</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/720aba5c-246b-4577-ae78-aec685245009-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/720aba5c-246b-4577-ae78-aec685245009-3807603.jpg"></p>
<p>f中的-1就变成没有意义，因为没有第-1行，而weights[0], values[0]继续有效，${f(0,j)}$也有意义，因为我们全部放到一个一维数组中。于是:</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/ff668590-d503-4d05-beae-3561d7955905-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/ff668590-d503-4d05-beae-3561d7955905-3807603.jpg"></p>
<p>这方程后面多加了一个限制条件，要求是从大到小循环。为什么呢？</p>
<p>假设有物体${\cal z}$容量2，价值${v_z}$很大，背包容量为5，如果j的循环顺序不是逆序，那么外层循环跑到物体${\cal z}$时， 内循环在${j=2}$时 ，${\cal z}$被放入背包。当${j=4}$时，寻求最大价值，物体z放入背包，${f(4)=max(f(4),f(2)+v_z) }$， 这里毫无疑问后者最大。 但此时${f(2)+v_z}$中的${f(2)}$ 已经装入了一次${\cal z}$，这样一来${\cal z}$被装入两次不符合要求， 如果逆序循环j， 这一问题便解决了。</p>
<p>javascript实现：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">//by 司徒正美</span>
<span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j <span class="token operator">=</span> <span class="token constant">W</span><span class="token punctuation">;</span> j <span class="token operator">>=</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> j<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>  
            f<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span>values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>f<span class="token punctuation">.</span><span class="token function">concat</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token comment">//调试</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/c1a1fc4e-4692-408d-96dd-9e7913e3896b-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/c1a1fc4e-4692-408d-96dd-9e7913e3896b-3807603.jpg"></p>
<h3 id="1-4-递归法解01背包"><a href="#1-4-递归法解01背包" class="headerlink" title="1.4 递归法解01背包"></a>1.4 递归法解01背包</h3><p>由于这不是动态规则的解法，大家多观察方程就理解了：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">//by 司徒正美</span>
<span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">n<span class="token punctuation">,</span> <span class="token constant">W</span><span class="token punctuation">,</span> weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> selected</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> <span class="token constant">W</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token comment">//当物品数量为0，或者背包容量为0时，最优解为0</span>
        <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
        <span class="token comment">//从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token comment">//如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品</span>
            <span class="token comment">//在这种情况的最优解为f(n-1,C)</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span> <span class="token constant">W</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                <span class="token keyword">return</span> <span class="token function">knapsack</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token constant">W</span><span class="token punctuation">,</span> weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> selected<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
                <span class="token keyword">var</span> a <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token constant">W</span><span class="token punctuation">,</span> weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> selected<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//不选择物品i的情况下的最优解</span>
                <span class="token keyword">var</span> b <span class="token operator">=</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token function">knapsack</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token constant">W</span> <span class="token operator">-</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> selected<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//选择物品i的情况下的最优解</span>
                <span class="token comment">//返回选择物品i和不选择物品i中最优解大的一个</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>a <span class="token operator">></span> b<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                    selected<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">//这种情况下表示物品i未被选取</span>
                    <span class="token keyword">return</span> a<span class="token punctuation">;</span>
                <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
                    selected<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">//物品i被选取</span>
                    <span class="token keyword">return</span> b<span class="token punctuation">;</span>
                <span class="token punctuation">&#125;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>        
<span class="token keyword">var</span> selected <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> ws <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">,</span> vs <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">]</span>
<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">,</span> ws<span class="token punctuation">,</span> vs<span class="token punctuation">,</span> selected<span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span> <span class="token comment">//15</span>
selected<span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">el<span class="token punctuation">,</span>i</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>el<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token string">"选择了物品"</span><span class="token operator">+</span>i<span class="token operator">+</span> <span class="token string">" 其重量为"</span><span class="token operator">+</span> ws<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+</span><span class="token string">" 其价值为"</span><span class="token operator">+</span>vs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/8b57fb10-e0c0-4d26-a955-fba4f1a01b58-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/8b57fb10-e0c0-4d26-a955-fba4f1a01b58-3807603.jpg"></p>
<h2 id="完全背包问题"><a href="#完全背包问题" class="headerlink" title="完全背包问题"></a>完全背包问题</h2><h3 id="2-1-问题描述："><a href="#2-1-问题描述：" class="headerlink" title="2.1 问题描述："></a>2.1 问题描述：</h3><p>有${n}$件物品和${1}$个容量为W的背包。每种物品没有上限，第${i}$件物品的重量为${weights[i]}$，价值为${values[i]}$，求解将哪些物品装入背包可使价值总和最大。</p>
<h3 id="2-2-问题分析："><a href="#2-2-问题分析：" class="headerlink" title="2.2 问题分析："></a>2.2 问题分析：</h3><p>最简单思路就是把完全背包拆分成01背包，就是把01背包中状态转移方程进行扩展，也就是说01背包只考虑放与不放进去两种情况，而完全背包要考虑 放0、放1、放2…的情况，</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/cb483fb8-a1b0-45a4-b135-edcdf5c04065-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/cb483fb8-a1b0-45a4-b135-edcdf5c04065-3807603.jpg"></p>
<p>这个k当然不是无限的，它受背包的容量与单件物品的重量限制，即${j/weights[i]}$。假设我们只有1种商品，它的重量为20，背包的容量为60，那么它就应该放3个，在遍历时，就0、1、2、3地依次尝试。</p>
<p>程序需要求解${n<em>W}$个状态，每一个状态需要的时间为${O（W/w_i）}$，总的复杂度为${O(nW</em>Σ(W/w_i))}$。</p>
<p>我们再回顾01背包经典解法的核心代码</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n <span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> 
   <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">&lt;=</span><span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> 
       f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span>values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
      <span class="token punctuation">&#125;</span>
   <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>现在多了一个k，就意味着多了一重循环</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n <span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> 
   <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">&lt;=</span><span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> 
       <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> k <span class="token operator">&lt;</span> j <span class="token operator">/</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
          f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>k<span class="token operator">*</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span>k<span class="token operator">*</span>values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token punctuation">&#125;</span>
      <span class="token punctuation">&#125;</span>
   <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>javascript的完整实现：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">completeKnapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    f<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token comment">//初始化边界</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> <span class="token constant">W</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        f<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>j <span class="token operator">&lt;=</span> <span class="token constant">W</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
            <span class="token keyword">var</span> bound <span class="token operator">=</span> j <span class="token operator">/</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>k <span class="token operator">&lt;=</span> bound<span class="token punctuation">;</span>k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> k <span class="token operator">*</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> k <span class="token operator">*</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token comment">//物品个数n = 3，背包容量为W = 5，则背包可以装下的最大价值为40.</span>
<span class="token keyword">var</span> a <span class="token operator">=</span> <span class="token function">completeKnapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token punctuation">,</span><span class="token number">20</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">)</span> 
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span> <span class="token comment">//40</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h3 id="2-3-O-nW-优化"><a href="#2-3-O-nW-优化" class="headerlink" title="2.3 O(nW)优化"></a>2.3 O(nW)优化</h3><p>我们再进行优化，改变一下f思路，让${f(i,j)}$表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。</p>
<p>所以说，对于第i件物品有放或不放两种情况，而放的情况里又分为放1件、2件、……${j/w_i}$件</p>
<p>如果不放, 那么${f(i,j)=f(i-1,j)}$；如果放，那么当前背包中应该出现至少一件第i种物品，所以f(i,j)中至少应该出现一件第i种物品,即${f(i,j)=f(i,j-w_i)+v_i}$，为什么会是${f(i,j-w_i)+v_i}$？</p>
<p>因为我们要把当前物品i放入包内，因为物品i可以无限使用，所以要用${f(i,j-w_i)}$；如果我们用的是${f(i-1,j-w_i)}$，${f(i-1,j-w_i)}$的意思是说，我们只有一件当前物品i，所以我们在放入物品i的时候需要考虑到第i-1个物品的价值${f(i-1,j-w_i)}$；但是现在我们有无限件当前物品i，我们不用再考虑第i-1个物品了，我们所要考虑的是在当前容量下是否再装入一个物品i，而${(j-w_i)}$的意思是指要确保${f(i,j)}$至少有一件第i件物品，所以要预留c(i)的空间来存放一件第i种物品。总而言之，如果放当前物品i的话，它的状态就是它自己”i”，而不是上一个”i-1”。</p>
<p>所以说状态转移方程为：</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/f06f2ae8-e517-4daf-8a18-1763b4952fbf-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/f06f2ae8-e517-4daf-8a18-1763b4952fbf-3807603.jpg"></p>
<p>与01背包的相比，只是一点点不同，我们也不需要三重循环了</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/d601fb68-76db-4457-bcc2-781a4d6b86fb-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/d601fb68-76db-4457-bcc2-781a4d6b86fb-3807603.jpg"></p>
<p>javascript的完整实现：</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">unboundedKnapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
        n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    f<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">//初始化边界</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> <span class="token constant">W</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        f<span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> <span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">&lt;</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
                f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">concat</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//调试</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">var</span> a <span class="token operator">=</span> <span class="token function">unboundedKnapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">,</span> <span class="token number">20</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//输出40</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">unboundedKnapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">9</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//输出12</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>我们可以继续优化此算法，可以用一维数组写</p>
<p>我们用${f(j)}$表示当前可用体积j的价值，我们可以得到和01背包一样的递推式：</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/aa78d800-f6c3-4158-a487-ff69c13d4911-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/aa78d800-f6c3-4158-a487-ff69c13d4911-3807603.jpg"></p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">unboundedKnapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">,</span>
    f <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span> n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span>j <span class="token operator">=</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> <span class="token constant">W</span><span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
          <span class="token keyword">var</span> tmp <span class="token operator">=</span> f<span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span>values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
          f<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>f<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">></span> tmp<span class="token punctuation">)</span> <span class="token operator">?</span> f<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">:</span> tmp<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>f<span class="token punctuation">)</span><span class="token comment">//调试</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">var</span> a <span class="token operator">=</span> <span class="token function">unboundedKnapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">,</span> <span class="token number">20</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//输出40</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">unboundedKnapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">9</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//输出12</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h2 id="多重背包问题"><a href="#多重背包问题" class="headerlink" title="多重背包问题"></a>多重背包问题</h2><h3 id="3-1-问题描述："><a href="#3-1-问题描述：" class="headerlink" title="3.1 问题描述："></a>3.1 问题描述：</h3><p>有${n}$件物品和${1}$个容量为W的背包。每种物品最多有numbers[i]件可用，第${i}$件物品的重量为${weights[i]}$，价值为${values[i]}$，求解将哪些物品装入背包可使价值总和最大。</p>
<h3 id="3-2-问题分析："><a href="#3-2-问题分析：" class="headerlink" title="3.2 问题分析："></a>3.2 问题分析：</h3><p>多重背包就是一个进化版完全背包。在我们做完全背包的第一个版本中，就是将它转换成01背包，然后限制k的循环</p>
<p>直接套用01背包的一维数组解法</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> numbers<span class="token punctuation">,</span>  <span class="token constant">W</span></span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    <span class="token keyword">var</span> f<span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> k<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> k<span class="token operator">&lt;</span>numbers<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span><span class="token comment">//其实就是把这类物品展开，调用numbers[i]次01背包代码  </span>
         <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">var</span> j<span class="token operator">=</span><span class="token constant">W</span><span class="token punctuation">;</span> j<span class="token operator">>=</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> j<span class="token operator">--</span><span class="token punctuation">)</span><span class="token comment">//正常的01背包代码  </span>
             f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>f<span class="token punctuation">[</span>j<span class="token operator">-</span>weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span>values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>  
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">knapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">1</span> <span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h3 id="3-3-使用二进制优化"><a href="#3-3-使用二进制优化" class="headerlink" title="3.3 使用二进制优化"></a>3.3 使用二进制优化</h3><p>其实说白了我们最朴素的多重背包做法是将有数量限制的相同物品看成多个不同的0-1背包。这样的时间复杂度为${O(W<em>Σn(i))}$, W为空间容量 ，n(i)为每种背包的数量限制。如果这样会超时，我们就得考虑更优的拆分方法，由于拆成1太多了，我们考虑拆成二进制数，对于13的数量，我们拆成1，2，4，6（有个6是为了凑数）。 19 我们拆成1，2，4，8，4 （最后的4也是为了凑和为19）。经过这个样的拆分我们可以组合出任意的小于等于n(i)的数目（二进制啊，必然可以）。j极大程度缩减了等效为0-1背包时候的数量。 大概可以使时间复杂度缩减为${O(W</em>log(ΣN(i))}$；</p>
<p>定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1&gt;0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。</p>
<p>证明如下：</p>
<ol>
<li>数列1,2,4,…,2^(k-1)^,n-2^k+1^中所有元素的和为n，所以若干元素的和的范围为：[1, n]；</li>
<li>如果正整数t&lt;= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0<em>2^0+a1</em>2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.^</li>
<li>如果t&gt;=2^k 设s=n-2^k+1，则t-s&lt;=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。</li>
</ol>
<p>（证毕！）</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">mKnapsack</span><span class="token punctuation">(</span><span class="token parameter">weights<span class="token punctuation">,</span> values<span class="token punctuation">,</span> numbers<span class="token punctuation">,</span> <span class="token constant">W</span></span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">var</span> kind <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">//新的物品种类</span>
    <span class="token keyword">var</span> ws <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">//新的物品重量</span>
    <span class="token keyword">var</span> vs <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">//新的物品价值</span>
    <span class="token keyword">var</span> n <span class="token operator">=</span> weights<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    <span class="token comment">/**
     * 二进制分解
     * 100=1+2+4+8+16+32+37，观察可以得出100以内任何一个数都可以由以上7个数选择组合得到，
     * 所以对物品数目就不是从0都100遍历，而是0，1，2，4，8，16，32，37遍历，时间大大优化。
     */</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">var</span> w <span class="token operator">=</span> weights<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">var</span> v <span class="token operator">=</span> values<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">var</span> num <span class="token operator">=</span> numbers<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">;</span> j <span class="token operator">*=</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>num <span class="token operator">>=</span> j<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
                ws<span class="token punctuation">[</span>kind<span class="token punctuation">]</span> <span class="token operator">=</span> j <span class="token operator">*</span> w<span class="token punctuation">;</span>
                vs<span class="token punctuation">[</span>kind<span class="token punctuation">]</span> <span class="token operator">=</span> j <span class="token operator">*</span> v<span class="token punctuation">;</span>
                num <span class="token operator">-=</span> j<span class="token punctuation">;</span>
                kind<span class="token operator">++</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
                ws<span class="token punctuation">[</span>kind<span class="token punctuation">]</span> <span class="token operator">=</span> num <span class="token operator">*</span> w<span class="token punctuation">;</span>
                vs<span class="token punctuation">[</span>kind<span class="token punctuation">]</span> <span class="token operator">=</span> num <span class="token operator">*</span> v<span class="token punctuation">;</span>
                kind<span class="token operator">++</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token comment">//01背包解法</span>
    <span class="token keyword">var</span> f <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span><span class="token constant">W</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> kind<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token constant">W</span><span class="token punctuation">;</span> j <span class="token operator">>=</span> ws<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> j<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            f<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> f<span class="token punctuation">[</span>j <span class="token operator">-</span> ws<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> vs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> f<span class="token punctuation">[</span><span class="token constant">W</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">var</span> b <span class="token operator">=</span> <span class="token function">mKnapsack</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">1</span> <span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span> <span class="token comment">//9</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h2 id="参考链接"><a href="#参考链接" class="headerlink" title="参考链接"></a>参考链接</h2><p><a target="_blank" rel="noopener" href="https://segmentfault.com/a/1190000012829866">javascript背包问题详解</a></p>

  </div>
  <div>
    
  </div>
</article>
<div class="nav">
  
    <div class="nav-item-prev">
      <a 
        href="/2021/10/17/TLSAndSSLWorkingPrincipleAndHandshakeProcessInDetail/" 
        class="nav-link">
        <i class="iconfont icon-left nav-prev-icon"></i>
        <div>
          <div class="nav-label">上一篇</div>
          
            <div class="nav-title">TLS/SSL 工作原理及握手过程详解 </div>
          
        </div>
      </a>
    </div>
  
  
    <div class="nav-item-next">
      <a 
        href="/2021/10/17/theDifferenceBetweenHTTPAndHTTPS/" 
        class="nav-link">
        <div>
          <div class="nav-label">下一篇</div>
          
            <div class="nav-title">HTTP 和 HTTPS 的区别（面试常考题） </div>
          
        </div>
        <i class="iconfont icon-right nav-next-icon"></i>
      </a>
    </div>
  
</div>

<div 
  class="card card-content toc-card" 
  id="mobiletoc">
  <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BC%95%E5%AD%90"><span class="toc-text">引子</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">01背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">1.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">1.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-%E5%90%84%E7%A7%8D%E4%BC%98%E5%8C%96%EF%BC%9A"><span class="toc-text">1.3 各种优化：</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%90%88%E5%B9%B6%E5%BE%AA%E7%8E%AF"><span class="toc-text">合并循环</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%80%89%E6%8B%A9%E7%89%A9%E5%93%81"><span class="toc-text">选择物品</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84%E5%8E%8B%E7%BC%A9%E7%A9%BA%E9%97%B4"><span class="toc-text">使用滚动数组压缩空间</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8%E4%B8%80%E7%BB%B4%E6%95%B0%E7%BB%84%E5%8E%8B%E7%BC%A9%E7%A9%BA%E9%97%B4"><span class="toc-text">使用一维数组压缩空间</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-%E9%80%92%E5%BD%92%E6%B3%95%E8%A7%A301%E8%83%8C%E5%8C%85"><span class="toc-text">1.4 递归法解01背包</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">完全背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">2.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">2.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-O-nW-%E4%BC%98%E5%8C%96"><span class="toc-text">2.3 O(nW)优化</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">多重背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">3.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">3.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-3-%E4%BD%BF%E7%94%A8%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%BC%98%E5%8C%96"><span class="toc-text">3.3 使用二进制优化</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
</div></main>
            <aside class="left-column">
              
              <div class="card card-author">
                
  <img 
    src="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg" 
    class="author-img" 
    alt="author avatar">

<p class="author-name">霜序廿</p>
<p class="author-description">无限进步</p>
<div class="author-message">
  <a 
    class="author-posts-count" 
    href="/archives">
    <span>253</span>
    <span>文章</span>
  </a>
  <a 
    class="author-categories-count" 
    href="/categories">
    <span>6</span>
    <span>分类</span>
  </a>
  <a 
    class="author-tags-count" 
    href="/tags">
    <span>51</span>
    <span>标签</span>
  </a>
</div>

  <div class="author-card-society">
    
      <div class="author-card-society-icon">
        <a target="_blank" rel="noopener" href="https://github.com/shuangxunian">
          <i class="iconfont icon-github society-icon"></i>
        </a>
      </div>
    
      <div class="author-card-society-icon">
        <a target="_blank" rel="noopener" href="https://space.bilibili.com/391117803">
          <i class="iconfont icon-bilibili society-icon"></i>
        </a>
      </div>
    
  </div>

              </div>
               <div class="sticky-tablet">
  
  
    <article class="display-when-two-columns spacer">
      <div class="card card-content toc-card">
        <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BC%95%E5%AD%90"><span class="toc-text">引子</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">01背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">1.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">1.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-%E5%90%84%E7%A7%8D%E4%BC%98%E5%8C%96%EF%BC%9A"><span class="toc-text">1.3 各种优化：</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%90%88%E5%B9%B6%E5%BE%AA%E7%8E%AF"><span class="toc-text">合并循环</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%80%89%E6%8B%A9%E7%89%A9%E5%93%81"><span class="toc-text">选择物品</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84%E5%8E%8B%E7%BC%A9%E7%A9%BA%E9%97%B4"><span class="toc-text">使用滚动数组压缩空间</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8%E4%B8%80%E7%BB%B4%E6%95%B0%E7%BB%84%E5%8E%8B%E7%BC%A9%E7%A9%BA%E9%97%B4"><span class="toc-text">使用一维数组压缩空间</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-%E9%80%92%E5%BD%92%E6%B3%95%E8%A7%A301%E8%83%8C%E5%8C%85"><span class="toc-text">1.4 递归法解01背包</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">完全背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">2.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">2.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-O-nW-%E4%BC%98%E5%8C%96"><span class="toc-text">2.3 O(nW)优化</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">多重背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">3.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">3.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-3-%E4%BD%BF%E7%94%A8%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%BC%98%E5%8C%96"><span class="toc-text">3.3 使用二进制优化</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
      </div>
    </article>
  
  
  <article class="card card-content categories-widget">
    <div class="categories-card">
  <div class="categories-header">
    <i 
      class="iconfont icon-fenlei" 
      style="padding-right: 2px;">
    </i>分类
  </div>
  <div class="categories-list">
    
      <a href="/categories/%E6%8A%80%E6%9C%AF%E6%96%87%E7%AB%A0/">
        <div class="categories-list-item">
          技术文章
          <span class="categories-list-item-badge">218</span>
        </div>
      </a>
    
      <a href="/categories/%E5%85%B6%E4%BB%96/">
        <div class="categories-list-item">
          其他
          <span class="categories-list-item-badge">16</span>
        </div>
      </a>
    
      <a href="/categories/%E6%97%85%E6%B8%B8/">
        <div class="categories-list-item">
          旅游
          <span class="categories-list-item-badge">1</span>
        </div>
      </a>
    
      <a href="/categories/%E7%AE%97%E6%B3%95/">
        <div class="categories-list-item">
          算法
          <span class="categories-list-item-badge">8</span>
        </div>
      </a>
    
      <a href="/categories/%E8%80%83%E8%AF%95/">
        <div class="categories-list-item">
          考试
          <span class="categories-list-item-badge">8</span>
        </div>
      </a>
    
      <a href="/categories/%E9%98%85%E8%AF%BB/">
        <div class="categories-list-item">
          阅读
          <span class="categories-list-item-badge">1</span>
        </div>
      </a>
    
  </div>
</div>
  </article>
  
  <article class="card card-content tags-widget">
    <div class="tags-card">
  <div class="tags-header">
    <i 
      class="iconfont icon-biaoqian" 
      style="padding-right: 2px;">
    </i>热门标签
  </div>
  <div class="tags-list">
    
      <a 
        href="/tags/js/" 
        title="js">
        <div class="tags-list-item">js</div>
      </a>
    
      <a 
        href="/tags/vue/" 
        title="vue">
        <div class="tags-list-item">vue</div>
      </a>
    
      <a 
        href="/tags/%E9%9D%A2%E8%AF%95/" 
        title="面试">
        <div class="tags-list-item">面试</div>
      </a>
    
      <a 
        href="/tags/css/" 
        title="css">
        <div class="tags-list-item">css</div>
      </a>
    
      <a 
        href="/tags/%E7%BD%91%E7%BB%9C/" 
        title="网络">
        <div class="tags-list-item">网络</div>
      </a>
    
      <a 
        href="/tags/%E5%85%B6%E4%BB%96/" 
        title="其他">
        <div class="tags-list-item">其他</div>
      </a>
    
      <a 
        href="/tags/%E7%AE%97%E6%B3%95/" 
        title="算法">
        <div class="tags-list-item">算法</div>
      </a>
    
      <a 
        href="/tags/%E6%B5%8F%E8%A7%88%E5%99%A8/" 
        title="浏览器">
        <div class="tags-list-item">浏览器</div>
      </a>
    
      <a 
        href="/tags/html/" 
        title="html">
        <div class="tags-list-item">html</div>
      </a>
    
      <a 
        href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" 
        title="操作系统">
        <div class="tags-list-item">操作系统</div>
      </a>
    
      <a 
        href="/tags/%E8%80%83%E8%AF%95/" 
        title="考试">
        <div class="tags-list-item">考试</div>
      </a>
    
      <a 
        href="/tags/%E8%BD%AF%E5%AE%9E%E5%8A%9B/" 
        title="软实力">
        <div class="tags-list-item">软实力</div>
      </a>
    
      <a 
        href="/tags/DOM/" 
        title="DOM">
        <div class="tags-list-item">DOM</div>
      </a>
    
      <a 
        href="/tags/%E8%BD%AE%E5%AD%90/" 
        title="轮子">
        <div class="tags-list-item">轮子</div>
      </a>
    
      <a 
        href="/tags/%E7%BD%91%E7%BB%9C%E5%8E%9F%E7%90%86/" 
        title="网络原理">
        <div class="tags-list-item">网络原理</div>
      </a>
    
      <a 
        href="/tags/debug/" 
        title="debug">
        <div class="tags-list-item">debug</div>
      </a>
    
  </div>
</div>
  </article>
  
  
</div>
            </aside>
            <aside class="right-column">
              <div class="sticky-widescreen">
  
  
    <article class="card card-content toc-card">
      <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BC%95%E5%AD%90"><span class="toc-text">引子</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">01背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">1.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">1.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-%E5%90%84%E7%A7%8D%E4%BC%98%E5%8C%96%EF%BC%9A"><span class="toc-text">1.3 各种优化：</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%90%88%E5%B9%B6%E5%BE%AA%E7%8E%AF"><span class="toc-text">合并循环</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%80%89%E6%8B%A9%E7%89%A9%E5%93%81"><span class="toc-text">选择物品</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84%E5%8E%8B%E7%BC%A9%E7%A9%BA%E9%97%B4"><span class="toc-text">使用滚动数组压缩空间</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BD%BF%E7%94%A8%E4%B8%80%E7%BB%B4%E6%95%B0%E7%BB%84%E5%8E%8B%E7%BC%A9%E7%A9%BA%E9%97%B4"><span class="toc-text">使用一维数组压缩空间</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-%E9%80%92%E5%BD%92%E6%B3%95%E8%A7%A301%E8%83%8C%E5%8C%85"><span class="toc-text">1.4 递归法解01背包</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">完全背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">2.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">2.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-O-nW-%E4%BC%98%E5%8C%96"><span class="toc-text">2.3 O(nW)优化</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">多重背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">3.1 问题描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-2-%E9%97%AE%E9%A2%98%E5%88%86%E6%9E%90%EF%BC%9A"><span class="toc-text">3.2 问题分析：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-3-%E4%BD%BF%E7%94%A8%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%BC%98%E5%8C%96"><span class="toc-text">3.3 使用二进制优化</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
    </article>
  
  
  <article class="card card-content">
    <div class="recent-posts-card">
  <div class="recent-posts-header">
    <i 
      class="iconfont icon-wenzhang_huaban" 
      style="padding-right: 2px;">
    </i>最近文章
  </div>
  <div class="recent-posts-list">
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-05-01</div>
        <a href="/2022/05/01/typescriptHome/"><div class="recent-posts-item-content">typescript</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptTheVariousWaysAndAdvantagesAndDisadvantagesOfDeepInheritance/"><div class="recent-posts-item-content">JavaScript深入之继承的多种方式和优缺点</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptGoFromPrototypeToPrototypeChain/"><div class="recent-posts-item-content">JavaScript深入之从原型到原型链</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptMemoryLeakTutorial/"><div class="recent-posts-item-content">JavaScript 内存泄漏教程</div></a>
      </div>
    
  </div>
</div>
  </article>
  
  
  
  <article class="card card-content">
    <div class="recent-posts-card">
  <div class="recent-posts-header">
    关注嘉然！顿顿解馋！
  </div>
  <div class="recent-posts-list">
    
      <img 
        src="https://api2.mubu.com/v3/document_image/2697c6ae-10ee-41a3-9099-304bdb252d31-3807603.jpg" 
        class="myadd-img" 
        alt="author avatar">
    
  </div>
</div>
  </article>
</div>
            </aside>
          </div>
        </div>
      </div>
    </div>
     
    <footer class="footer">
  <div class="footer-container">
    <div>
      <div class="footer-dsc">
        <span>
          Copyright ©
          
            2020 -
          
          2022
        </span>
        &nbsp;
        <a 
          href="/" 
          class="footer-link">
          霜序廿的个人网站
        </a>
      </div>
    </div>

    
      <div class="footer-dsc">
        
          Powered by
          <a 
            href="https://hexo.io/" 
            class="footer-link" 
            target="_blank" 
            rel="nofollow noopener noreferrer">
            &nbsp;Hexo
          </a>
        
        
          <span>&nbsp;|&nbsp;</span>
        
        
          Theme -
          <a 
            href="https://github.com/theme-kaze" 
            class="footer-link" 
            target="_blank"
            rel="nofollow noopener noreferrer">
            &nbsp;Kaze
          </a>
        
      </div>
    
    
    
    
</footer> 
    
  <a 
    role="button" 
    id="scrollbutton" 
    class="basebutton" 
    aria-label="回到顶部">
    <i class="iconfont icon-arrowleft button-icon"></i>
  </a>

<a 
  role="button" 
  id="menubutton" 
  class="basebutton">
  <i class="iconfont icon-menu button-icon"></i>
</a>
<a 
  role="button" 
  id="popbutton" 
  class="basebutton" 
  aria-label="控制中心">
  <i class="iconfont icon-expand button-icon"></i>
</a>
<a 
  role="button" 
  id="darkbutton" 
  class="basebutton darkwidget" 
  aria-label="夜色模式">
  <i class="iconfont icon-weather button-icon"></i>
</a>
<a 
  role="button" 
  id="searchbutton" 
  class="basebutton searchwidget" 
  aria-label="搜索">
  <i class="iconfont icon-search button-icon"></i>
</a> 
     
     
     
      <script>
  var addImgLayout = function () {
    var img = document.querySelectorAll('.post-content img')
    var i
    for (i = 0; i < img.length; i++) {
      var wrapper = document.createElement('a')
      wrapper.setAttribute('href', img[i].getAttribute('data-src'))
      wrapper.setAttribute('aria-label', 'illustration')
      wrapper.style.cssText =
        'width: 100%; display: flex; justify-content: center;'
      if (img[i].alt) wrapper.dataset.caption = img[i].alt
      wrapper.dataset.nolink = true
      img[i].before(wrapper)
      wrapper.append(img[i])
      var divWrap = document.createElement('div')
      divWrap.classList.add('gallery')
      wrapper.before(divWrap)
      divWrap.append(wrapper)
    }
    baguetteBox.run('.gallery')
  }
</script>
<script>
  loadScript(
    "/js/lib/lightbox/baguetteBox.min.js",
    addImgLayout
  )
</script>
 
     
     
    <script src="/js/main.js"></script> 
     
    
      <script>
        var addLazyload = function () {
          var observer = lozad('.lozad', {
            load: function (el) {
              el.srcset = el.getAttribute('data-src')
            },
            loaded: function (el) {
              el.classList.add('loaded')
            },
          })
          observer.observe()
        }
      </script>
      <script>
        loadScript('/js/lib/lozad.min.js', addLazyload)
      </script>
     
    
    
  </body>
</html>
